class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        //dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                dp[i][j] = matrix[i - 1][j - 1] - '0' + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
        int side = min(m, n), ret = 0;
        for (int len = 1; len <= side; len++)
        {
            for (int i = len; i <= m; i++)
            {
                for (int j = len; j <= n; j++)
                {
                    int r1 = i - len, c1 = j - len;
                    int r2 = i, c2 = j;
                    if (dp[r2][c2] - dp[r1][c2] - dp[r2][c1] + dp[r1][c1] == len * len)
                        ret = max(ret, len * len);
                }
            }
        }
        return ret;
    }
};